package com.LeeCode;

import java.util.*;

/**
 * 全排列 II
 */

public class Code047 {
    public static void main(String[] args) {
        int[] nums = {1, 1, 2};
        System.out.println(new Code047().permuteUnique(nums));
    }

    private int[] pre = new int[8];

    public List<List<Integer>> permuteUnique(int[] nums) {
        List<List<Integer>> ans = new ArrayList<>();
        List<Integer> list = Arrays.asList(new Integer[nums.length]); // 所有排列的长度都是一样的 n

        // 预处理前一个相同元素出现位置的数组
        for (int i = 0; i < nums.length; i++) {
            pre[i] = -1;
            for (int j = i - 1; j >= 0; j--) {
                if (nums[j] == nums[i]) {
                    pre[i] = j;
                    break;
                }
            }
        }

        // 回溯生成全排列
        backtrace(0, list, ans, new boolean[nums.length], nums);
        return ans;
    }

    private void backtrace(int index, List<Integer> list, List<List<Integer>> ans, boolean[] visited, int[] nums) {
        if (index == nums.length) { // 记录答案
            ans.add(new ArrayList<>(list));
            return;
        }

        for (int i = 0; i < nums.length; i++) {
            /**
             * 选取可能元素
             * 1. 第一次出现且未被访问
             * 2. 未被访问过且前一个相同元素已经被访问过
             */
            if (!visited[i] && (pre[i] == -1 || visited[pre[i]])) {
                visited[i] = true;
                list.set(index, nums[i]);
                backtrace(index + 1, list, ans, visited, nums);
                visited[i] = false;

            }
        }
    }


    public List<List<Integer>> permuteUnique1(int[] nums) {
        List<List<Integer>> ans = new ArrayList<>();
        List<Integer> list = new ArrayList<>();
        Set<Integer>[] cnt = new Set[nums.length];
        Arrays.setAll(cnt, k -> new HashSet<Integer>());

        backtrace(0, list, ans, new boolean[nums.length], nums, cnt);
        return ans;
    }

    private void backtrace(int index, List<Integer> list, List<List<Integer>> ans,
                           boolean[] visited, int[] nums, Set<Integer>[] cnt) {
        if (index == nums.length) {  // 记录答案
            ans.add(new ArrayList<>(list));
            return;
        }

        int pos = list.size(); // 当前在选第几个元素
        for (int i = 0; i < nums.length; i++) {
            if (!visited[i] && !cnt[pos].contains(nums[i])) { // 没有选过且未重复
                visited[i] = true;
                list.add(nums[i]);
                cnt[pos].add(nums[i]);
                backtrace(index + 1, list, ans, visited, nums, cnt);
                visited[i] = false;
                list.remove(list.size() - 1);
            }
        }
        cnt[pos].clear();
    }

}
